Metode numerice - Aplicatii

Lucrarea 6.   Rezolvarea sistemelor de ecuatii liniare cu metode iterative: metodele Jacobi, Seidel-Gauss si suprarelaxarii succesive

Tema A - Metoda iterativa Jacobi
Tema B - Metoda iterativa Seidel-Gauss
Tema C - Metoda suprarelaxarii succesive

        Determinarea solutiei exacte a sistemului A * x = b cu ajutorul unor metode de tip iterativ este posibila numai dupa efectuarea unui numar nelimitat - teoretic infinit - de iteratii sau pasi. Deoarece nici o metoda practica nu poate cicla la infinit, rezulta ca metodele iterative determina doar o solutie aproximativa, aproximare prin trunchiere, care se abate mai mult sau mai putin fata de solutia exacta x*, in functie de precizia de calcul dorita.
        Mai concret, metodele iterative apeleaza la construirea unui sir de aproximatii succesive x_0, x_1, ... , x_k care, in anumite conditii, tinde catre solutia exacta  x*. In cazul in care pentru sirul aproximatiilor succesive nu este posibila definirea unei limite, se spune ca metoda respectiva diverge.
        In cazul in care sirul aproximatiilor succesive are o limita, se spune ca metoda este convergenta. In acest caz se poate defini o relatie de recurenta intre doua aproximatii succesive x_k si x_(k+1). Definirea relatiei de recurenta intre aproximatiile succesive se face pornind de la desfacerea matricei A in alte doua matrice:

A = N - P
Folosind aceasta desfacere in expresia sistemului de ecuatii se obtine relatia:
 N * x = P * x + b
care permite ca, pornind de la o aproximatie initiala x_0, sa se construiasca un sir de aproximatii succesive pe baza relatiei de recurenta:
N * x_(k+1) = P * x_k + b
In practica, alegerea desfacerii A = N - P se face astfel incat un sistem de forma N * y = C, unde y si C sunt vectori ai necunoscutelor si termenilor liberi, sa se  rezolve cat mai usor. Aceasta este totuna cu o forma cat mai simpla a matricei N, diagonala sau triunghiulara.
        In general, toate metodele iterative de rezolvare a sistemelor de ecuatii liniare, definesc matricele N si P din desfacerea A = N - P pornind de la desfacerea standard a matricei A:
A = L + D + R
unde: L este matricea strict inferior triunghiulara ale carei elemente subdiagonale sunt elementele matricei A; R este matricea strict superior triunghiulara ale carei elemente supradiagonale sunt elementele matricei A; D este matricea diagonala ale carei elemente nenule sunt tocmai elementele diagonale din matricea A.
        Ca si in cazul metodelor directe, toate metodele iterative folosesc impartirea la un element diagonal, numit pivot. Din acest motiv, desfacerea standard astfel definita trebuie sa se caracterizeze prin elemente nenule pe diagonala matricei D sau, ceea ce este totuna, pe diagonala matricei A. Daca exista cel putin un asemenea element nul este necesara permutarea unor linii ale matricei A (pivotarea partiala).

Tema A - Metoda iterativa Jacobi

        Metoda iterativa Jacobi, numita si metoda iteratiilor simultane, foloseste o desfacere A = N - P, in care matricele N si P se aleg conform relatiei:

N = D

P = - L - R

unde D, L si R sunt matricele din desfacerea standard, iar toate elementele diagonale a_ii sunt nenule. Folosind aceasta desfacere in relatia generala de recurenta, se obtine forma matriceala a relatiei de recurenta pentru metoda Jacobi:
D * x_(k+1) = - ( L + R ) * x_k + b
Pentru un element x_i al vectorului necunoscutelor, la iteratia k+1, relatia de recurenta capata forma:
care reprezinta formula de iterare a metodei Jacobi. Inspectia sumara a acestei formule sugereaza imediat motivul  pentru care toate elementele diagonale a_ii trebuie sa fie nenule.
        Metoda iterativa Jacobi este convergenta daca, pentru fiecare linie din matricea A, suma valorilor absolute ale termenilor din afara diagonalei principale nu depaseste valoarea absoluta a termenului diagonal. Matricele care satisfac aceasta proprietate se numesc diagonal dominante.
        O particularitate a metodei Jacobi se refera la modul cum este folosita aproximatia anterioara x_k pentru calculul noii aproximatii x_(k+1). Astfel, se constata ca noile aproximatii ale fiecarei necunoscutese determina în functie de aproximatiile anterioare ale tuturor celorlalte necunoscute ( j <> i ). Din acest motiv, noua aproximatie nu o poate inlocui pe cea anterioara în vectorul x si, in consecinta, aplicarea metodei Jacobi necesita folosirea a cel putin doi vectori : un vector x, care memoreaza  aproximatia anterioara si un vector y, care memoreaza aproximatia nou calculata. La sfarsitul fiecarei iteratii vectorul x este actualizat, prin copierea in el a elementelor vectorului y.


Algoritmul 1 - Sisteme de ecuatii liniare - Metoda iterativa Jacobi
  1. Definirea sistemului de ecuatii: rangul n, matricea coeficientilor A, vectorul termenilor liberi b;
  2. Definirea parametrilor de iterare: abaterea relativa maxima admisa Emax si numarul maxim de iteratii Nmax;
  3. Calcul iterativ:
    1. Stabilirea aproximatiei initiale, identica cu termenii liberi:
    2. Initializarea procesului iterativ: It <-- 0.
    3. Initializarea abaterii relative maxime in iteratia curenta cu o valoare superioara lui Emax : Dx <-- Emax + 1.
    4. Daca s-a atins numarul maxim de iteratii (It=Nmax) sau abaterea Dx a trecut sub valoarea admisa ( Dx <= Emax ), se incheie procesul iterativ si se trece la pasul 4;
    5. Trecerea la o noua iteratie: It <-- It + 1.
    6. Calculul noii aproximatii in vectorul y:
    7. Calculul abaterii relative maxime in iteratia curenta:
    8. Actualizarea vectorului aproximatiilor din ultima iteratie:
    9. Se revine la pasul 3.iv.
  4. Stabilirea conditiilor de iesire din bucla iterativa:
    • daca Dx <= Emax  (metoda converge), se afiseaza solutia aproximativasi numarul de iteratii efectuate It;
    • daca Dx>Emax, dar It=Nmax (metoda nu converge), se afiseaza mesajul "Depasire numar maxim iteratii";

Tema B - Metoda iterativa Seidel-Gauss

        Metoda iterativa Seidel - Gauss, numita si metoda iteratiilor succesive, foloseste o desfacere A = N - P, in care matricele N si P se aleg conform relatiei:

N = L + D
P = - R
unde D, L si R sunt matricele din desfacerea standard. Folosind aceasta desfacere in relatia generala de recurenta, se obtine:
( L + D ) * x_(k+1) = - R * x_k + b
care, particularizata pentru una din necunoscutele x_i, conduce la formula de iterare a metodei Seidel - Gauss:
        Ca si in cazul metodei Jacobi, aparitia termenilor a_ii la numitorul acestei expresii reflecta necesitatea ca toate elementele diagonale ale matricei A sa fie nenule.
        O comparatie intre formulele de iterare ale metodelor Jacobi si Seidel - Gauss evidentiaza urmatoarea particularitate:
  • in cazul metodei Jacobi noile aproximatii se determina folosind exclusiv aproximatiile din iteratia anterioara;
  • prin contrast, metoda Seidel-Gauss calculeaza noile aproximatii folosind si aproximatiile determinate deja in iteratia curenta (, j=1,...,i-1 ).
Consecinta imediata a acestei particularitati o reprezinta posibilitatea utilizarii unui singur vector pentru memorarea aproximatiilor succesive. Pe masura determinarii noilor aproximatii , acestea inlocuiesc in vectorul x vechile aproximatii , care nu mai sunt folosite in iteratia curenta.
        O alta consecinta a utilizarii aproximatiilor deja calculate pentru determinarea celorlalte aproximatii se refera la convergenta metodei. De regula, metoda Seidel - Gauss aduce un plus de viteza de convergenta fata de metoda Jacobi. Astfel, este de asteptat ca, pornind de la o aceeasi aproximatie initiala, metoda Seidel - Gauss sa asigure precizia impusa intr-un numar mai mic de iteratii.
        Ca si in cazul metodei Jacobi, conditia de convergenta a metodei Seidel - Gauss o reprezinta forma diagonal dominanta a matricei coeficientilor A.


Algoritmul 2 - Sisteme de ecuatii liniare - Metoda iterativa Seidel-Gauss
  1. Definirea sistemului de ecuatii: rangul n, matricea coeficientilor A, vectorul termenilor liberi b;
  2. Definirea parametrilor de iterare: abaterea relativa maxima admisa Emax si numarul maxim de iteratii Nmax;
  3. Calcul iterativ:
    1. Stabilirea aproximatiei initiale, identica cu termenii liberi:
    2. Initializarea procesului iterativ: It <-- 0.
    3. Initializarea abaterii relative maxime in iteratia curenta cu o valoare superioara lui Emax : Dx <-- Emax + 1.
    4. Daca s-a atins numarul maxim de iteratii (It=Nmax) sau abaterea Dx a trecut sub valoarea admisa ( Dx <= Emax ), se incheie procesul iterativ si se trece la pasul 4;
    5. Trecerea la o noua iteratie: It <-- It + 1.
    6. Initializarea abaterii relative maxime in iteratia curenta : Dx <-- 0;
    7. Calculul noii aproximatii si al abaterii relative maxime folosind o variabila tampon z:
    8. Se revine la pasul 3.iv.
  4. Stabilirea conditiilor de iesire din bucla iterativa:
    • daca Dx <= Emax (metoda converge), se afiseaza solutia aproximativasi numarul de iteratii efectuate It;
    • daca Dx>Emax, dar It=Nmax (metoda nu converge), se afiseaza mesajul "Depasire numar maxim iteratii";

Tema C - Metoda suprarelaxarii succesive

       Metoda suprarelaxarii succesive este o varianta modificata a metodei  iterative Seidel - Gauss, care urmareste accelerarea suplimentara a convergentei procesului iterativ. In acest scop, se utilizeaza o desfacere A = N - P care depinde de un parametru real, denumit parametru de accelerare (relaxare):

Matricele de desfacere N() si P() se pot alege arbitrar ca functii ale parametrului . Sa consideram insa cazul particular:
        Alegerea judicioasa a parametruluipoate determina cresterea ratei de convergenta. De fapt, pentru orice matrice A si pentru orice desfacere a acesteia de forma  se poate stabili o valoare optima a parametrului de accelerare , ca solutie a unei probleme de minimax (minimizarea unei valori maxime). Un alt avantaj al metodei suprarelaxarii succesive consta in posibilitatea transformarii unor procese divergente in procese convergente.
        Introducerea matricelor N() si P() astfel definite in relatia  de recurenta si particularizarea acesteia din urma pentru una dintre necunoscutele x_i, conduc la formula de iterare a metodei suprarelaxarii succesive:
        Comparand formula de iterare a metodei Seidel-Gauss cu relatia de mai sus se constata ca metoda suprarelaxarii succesive determina noua aproximatie prin aplicarea unei corectii (ultimul termen din relatie) aproximatiei calculate dupa metoda Seidel - Gauss. Aceasta corectie depinde de abaterile aproximatiilor in doua iteratii succesive - si de parametrul de accelerare .
        Pe de alta parte, se constata ca metoda suprarelaxarii succesive nu poate folosi direct formula de iterare, deoarece aceasta determina aproximatia in functie de ea insasi. Din acest motiv, algoritmul de calcul determina mai intai o solutie provizorie cu metoda Seidel-Gauss obisnuita, careia ii aplica apoi o corectie in functie de abaterea -:
Pentru aceasta formula se pot stabili doua expresii echivalente:
care introduc doi noi parametri de accelerare:
        Convergenta metodei Seidel - Gauss modificate, depinde in foarte mare masura de alegerea parametrilor de accelerare , si . Iata doua cazuri particulare:
  • =1, =0, =1. Aproximatiei nou calculate nu i se aplica nici o corectie. Se obtine metoda Seidel - Gauss obisnuita;
  • =1/2, =-1, =0 . Aproximatia nou calculata coincide cu aproximatia din iteratia anterioara. Procesul este stationar, toate aproximatiile ramanand identice cu aproximatia initiala.
        In practica, factorul de relaxare   se  alege  de  regula  in  intervalul ( 0 , 2 ) . Daca >2 procesul iterativ diverge in cele mai multe cazuri. In general, nu exista un criteriu unic de determinare a valorii optime a parametrului de accelerare , aceasta valoare fiind influentata de structura particulara a fiecarui sistem de ecuatii liniare analizat. Din acest motiv, se recomanda utilizarea cu prudenta a metodei suprarelaxarii succesive, iar atunci cand aceasta se aplica se recomanda folosirea unor parametri de accelerare cu valori in intervalul 1.4 - 1.5.
        In general, valori ale parametrului de accelerare 1 <  < 2 asigura accelerarea convergentei unor procese iterative deja convergente, in timp ce valori ale aceluiasi parametru  0 <  < 1 permit deseori transformarea unor procese divergente in procese convergente.


Algoritmul 3 - Sisteme de ecuatii liniare - Metoda suprarelaxarii succesive
  1. Definirea sistemului de ecuatii: rangul n, matricea coeficientilor A, vectorul termenilor liberi b;
  2. Definirea parametrilor de iterare: abaterea relativa maxima admisa Emax si numarul maxim de iteratii Nmax;
  3. Calcul iterativ:
    1. Stabilirea aproximatiei initiale, identica cu termenii liberi:
    2. Initializarea procesului iterativ: It <-- 0.
    3. Initializarea abaterii relative maxime in iteratia curenta cu o valoare superioara lui Emax : Dx <-- Emax + 1.
    4. Daca s-a atins numarul maxim de iteratii (It=Nmax) sau abaterea Dx a trecut sub valoarea admisa ( Dx <= Emax ), se incheie procesul iterativ si se trece la pasul 4;
    5. Trecerea la o noua iteratie: It <-- It + 1.
    6. Initializarea abaterii relative maxime in iteratia curenta : Dx <-- 0;
    7. Calculul noii aproximatii si al abaterii relative maxime folosind o variabila tampon z:
    8. Se revine la pasul 3.iv.
  4. Stabilirea conditiilor de iesire din bucla iterativa:
    • daca Dx <= Emax  (metoda converge), se afiseaza solutia aproximativasi numarul de iteratii efectuate It;
    • daca Dx>Emax, dar It=Nmax (metoda nu converge), se afiseaza mesajul "Depasire numar maxim iteratii";

Pentru detalii suplimenatare privind metodele iterative si convergenta procesului iterativ, se poate consulta cartea "Calcul numeric cu aplicatii in Turbo Pascal".
 

  Aplicatii - Lista lucrarilor de laborator